package com.carl.leetcode.string;

/**
 * Created by carlXie on 2016/1/14.
 * email: kkrimen@gmail.com
 */
public class LongestCommonPrefix {
    public static void main(String[] args) {
        String[] strs = {"carl is kkrimen", "carlxie", "carl is handsome", "carl is amber's bf"};

        long nano0 = System.nanoTime();
        System.out.println(longestCommonPrefix(strs));
        System.out.println(System.nanoTime() - nano0);

        long nano1 = System.nanoTime();
        System.out.println(longestCommonPrefix1(strs));
        System.out.println(System.nanoTime() - nano1);
    }

    public static String longestCommonPrefix(String[] strs) {
        int len = 0;
        if(strs.length > 0)
            len = strs[0].length();

        for (int i = 1; i < strs.length; i++) {
            len = Math.min(len, strs[i].length());
            int currentIndex = 0;
            while(currentIndex < len) {
                if(strs[0].charAt(currentIndex) != strs[i].charAt(currentIndex))
                    break;
                currentIndex ++;
            }
            len = currentIndex;
        }

        return len == 0 ? "" : strs[0].substring(0, len);
    }

    public static String longestCommonPrefix1(String[] strs) {
        int len = 0;
        if (strs.length == 0)
            return "";

        for (int i = 0; i < strs[0].length(); ++i) {
            for (int j = 1; j < strs.length; ++j) {
                if(i >= strs[j].length() || strs[0].charAt(i) != strs[j].charAt(i))
                    return strs[0].substring(0, len);
            }
            ++len;
        }

        return strs[0];
    }
}
